package leetcode.code0988;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

import leetcode.helper.H;
import leetcode.helper.tree.TreeArray;
import leetcode.helper.tree.TreeNode;

import leetcode.IDebug;

public class Solution implements IDebug {

	class Node {
		char c;
		Node next;

		public Node(char c) {
			this.c = c;
		}
	}

	List<Node> list;

	public String smallestFromLeaf(TreeNode root) {
		list = new ArrayList<>();
		this.smallest(root);
		StringBuffer ans = new StringBuffer();
		while (list.size() != 1) {
			ans.append(list.get(0).c);
			List<Node> nexts = new ArrayList<>();
			char cur = 0;
			for (int i = 0; i < list.size(); i++) {
				Node next = list.get(i).next;
				if (next == null) {
					return ans.toString();
				}
				if (nexts.size() == 0) {
					nexts.add(next);
					cur = next.c;
				} else if (next.c == cur) {
					nexts.add(next);
				} else if (next.c < cur) {
					nexts = new ArrayList<>();
					nexts.add(next);
					cur = next.c;
				}
			}
			list = nexts;
		}
		Node node = list.get(0);
		while (node != null) {
			ans.append(node.c);
			node = node.next;
		}
		return ans.toString();
	}

	private Node smallest(TreeNode root) {
		if (root == null) {
			return null;
		}
		char cur = (char) (root.val + 'a');
		Node head = new Node(cur);
		if (root.left == null && root.right == null) {
			if (list.size() == 0) {
				list.add(head);
				return head;
			}
			char c = list.get(0).c;
			if (c > cur) {
				list = new ArrayList<>();
				list.add(head);
				return head;
			} else if (c == cur) {
				list.add(head);
				return head;
			}
			return null;
		}
		Node left = this.smallest(root.left);
		if (left != null) {
			left.next = head;
		}
		Node right = this.smallest(root.right);
		if (right != null) {
			right.next = head;
		}
		return head;
	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug3() {
		this.smallestFromLeaf(TreeArray.array2tree(H.str2array4("[25,1,null,0,0,1,null,null,null,0]")));
	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
